package com.fanshuai.algorithms.branch;

import com.fanshuai.algorithms.datastructure.graph.IndirectGraph;
import com.fanshuai.queue.LinkedQueue;
import com.fanshuai.queue.Queue;

import java.util.ArrayList;
import java.util.List;

/**
 * 旅行商问题  分支限界法解决
 * 一销售商从n个城市中的某一城市出发，不重复地走完其余n—1个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条
 * n个城市构成一个图，使用邻接矩阵matrix表示图，matrix[i][j]表示城市i到j的距离
 *
 * 限界函数：!path.contains(i) && sumPath + matrix[cur][i] < minPath
 */
public class Travel {
    static class TravelNode {
        int i;
        int pathSum;
        List<Integer> path;

        public TravelNode(int i, int pathSum, List<Integer> path) {
            this.i = i;
            this.pathSum = pathSum;
            this.path = path;
        }
    }

    public static List<Integer> travel(int[][] matrix, int src) {
        int n = matrix.length - 1;

        int minPathSum = Integer.MAX_VALUE;
        List<Integer> minPath = new ArrayList<>();

        Queue<TravelNode> queue = new LinkedQueue<>();
        TravelNode node = new TravelNode(src, 0, new ArrayList<>());
        node.path.add(src);
        queue.enqueue(node);

        while (!queue.isEmpty()) {
            TravelNode cur = queue.dequeue();
            if (cur.path.size() == n) {
                int last = cur.path.get(cur.path.size() - 1);

                if (matrix[last][src] < Integer.MAX_VALUE && matrix[last][src] + cur.pathSum < minPathSum) {
                    minPathSum = matrix[last][src] + cur.pathSum;
                    minPath = new ArrayList<>(cur.path);
                    minPath.add(src);
                }
            }

            for (int i = 1; i <= n; i++) {
                boolean condition = !cur.path.contains(i) &&
                        cur.pathSum + matrix[cur.i][i] < minPathSum;

                if (matrix[cur.i][i] < Integer.MAX_VALUE && condition) {
                    TravelNode next = new TravelNode(i, cur.pathSum + matrix[cur.i][i], new ArrayList<>(cur.path));
                    next.path.add(i);

//                    System.out.println("node i=" + i + ", pathSum=" + cur.pathSum + matrix[cur.i][i] + ", path=" +
//                            next.path);

                    queue.enqueue(next);
                }
            }
        }

        System.out.println("min path=" + minPathSum);
        return minPath;
    }

    public static void main(String[] args) {
        int[][] a1 = new int[][] {{1, 2, 6}, {1, 3, 1}, {1, 4, 5}, {2, 3, 5}, {2, 5, 3}, {3, 4, 5},
                {3, 5, 6}, {3, 6, 4}, {4, 6, 2}, {5, 6, 6}};

        int[][] a2 = new int[][] {{1, 2, 3}, {1, 4, 8}, {1, 5, 9}, {2, 3, 3}, {2, 4, 10},
                {2, 5, 5}, {3, 4, 4}, {3, 5, 3}, {4, 5, 20}};

        IndirectGraph<Integer> graph = new IndirectGraph<>(6);
        for (int[] i : a1) {
            graph.addEdge(i[0], i[1], i[2]);
        }
        System.out.println(travel(graph.getMatrix(), 1));

        IndirectGraph<Integer> graph2 = new IndirectGraph<>(5);
        for (int[] i : a2) {
            graph2.addEdge(i[0], i[1], i[2]);
        }
        System.out.println(travel(graph2.getMatrix(), 1));
    }

}
